package DataStructe;

/**
 * Created by hasee on 2017/10/27.
 */
import ch16.BTNode;

import java.util.ArrayList;
import java.util.Scanner;

public class TreeReBuild {
    /*先序（DLR）、中序（LDR）遍历对应的三个数组*/
    static ArrayList<Integer> DLR=new ArrayList<Integer>();
    static ArrayList<Integer> LDR=new ArrayList<Integer>();
    static BTNode root = new BTNode(null);


    /*核心算法*/
    static void reBuildTreeprocess(BTNode x, ArrayList<Integer> qx, ArrayList<Integer> zx)
    {
        x.setElement(qx.get(0));//前序第一个元素必为根节点
        if(qx.size()<=1)
        {
            return;
        }

        x.setLeft(new BTNode(null));
        x.setRight(new BTNode(null));

        //两个序列的拆分索引
        int rootindex = 0;
        int qxindex=0;
        /*拆分序列*/
        ArrayList<Integer>newqxleft    = new ArrayList<Integer>();
        ArrayList<Integer>newqxright= new ArrayList<Integer>();
        ArrayList<Integer>newzxleft = new ArrayList<Integer>();
        ArrayList<Integer>newzxright = new ArrayList<Integer>();
        //拆分中序
        for(int j=0;j<zx.size();j++)
        {
            if(zx.get(j)==x.getElement())
            {
                zx.remove(j);
                j--;
                rootindex=j;
                break;
            }
        }

        //生成新的中序（左）
        for(int j=0;j<=rootindex;j++){

            newzxleft.add(zx.get(j));
        }
        //生成新的中序（右）
        for(int j=rootindex+1;j<zx.size();j++)
        {
            newzxright.add(zx.get(j));
        }



        //拆分前序，确定分离的元素索引
        if(newzxright.isEmpty())
        {
            //中序右为空，前序全为左子树
            for(int i=1;i<qx.size();i++)
            {
                newqxleft.add(qx.get(i));
            }
            x.setRight(null);
            reBuildTreeprocess(x.getLeft(), newqxleft, newzxleft);
        }
        else{
            if(newzxleft.isEmpty())
            {
                //中序左为空，前序全为右子树
                for(int i=1;i<qx.size();i++)
                {
                    newqxright.add(qx.get(i));
                }
                x.setLeft(null);
                reBuildTreeprocess(x.getRight(), newqxright, newzxright);
            }
            else {
                //均不为空，分别生成
                outer:        for(int r=0;r<qx.size();r++)
                {

                    for(int i=0;i<newzxright.size();i++)
                    {

                        if(qx.get(r)==newzxright.get(i))
                        {

                            qxindex=r;
                            break outer;
                        }
                    }
                }


                for(int t=1;t<qxindex;t++)
                {
                    newqxleft.add(qx.get(t));
                }
                for(int y=qxindex;y<qx.size();y++)
                {
                    newqxright.add(qx.get(y));
                }
                reBuildTreeprocess(x.getLeft(), newqxleft, newzxleft);
                reBuildTreeprocess(x.getRight(), newqxright, newzxright);
            }
        }
    }
    /*先序遍历，用于测试结果*/
    static void XSearch(BTNode x)
    {
        if (x==null) {
            return;
        }
        System.out.print(x.getElement()+",");
        if (x.getLeft()!=null) {
            XSearch(x.getLeft());
        }

        if(x.getRight()!=null){
            XSearch(x.getRight());
        }
    }



    /*中续遍历,用于测试结果*/
    static void ZSearch(BTNode x)
    {
        if (x==null) {
            return;
        }
        if (x.getLeft()!=null) {
            ZSearch(x.getLeft());
        }
        System.out.print(x.getElement()+",");
        if(x.getRight()!=null){
            ZSearch(x.getRight());
        }

    }


    /*后续遍历，用于测试结果*/
    static void HSearch(BTNode x)
    {
        if (x==null) {
            return;
        }
        if (x.getLeft()!=null) {
            HSearch(x.getLeft());
        }
        if(x.getRight()!=null){
            HSearch(x.getRight());
        }
        System.out.print(x.getElement()+",");
    }





    public static void main(String[] args) {
        Scanner getin = new Scanner(System.in);

        /*读入先序序列*/
        String readydata = getin.nextLine();
        String[] DLRdata = readydata.split(" ");
        for (int i = 0; i < DLRdata.length; i++) {
            int qxdata = Integer.parseInt(DLRdata[i]);
            DLR.add(qxdata);
        }


        /*读入中序序列*/
        readydata = getin.nextLine();
        String[] LDRdata = readydata.split(" ");
        for (int i = 0; i < LDRdata.length; i++) {
            int zxdata = Integer.parseInt(LDRdata[i]);
            LDR.add(zxdata);
        }
        reBuildTreeprocess(root, DLR, LDR);

        XSearch(root);
        System.out.println();
        ZSearch(root);
        System.out.println();
        HSearch(root);
        System.out.println();}}

